#include <bits/stdc++.h>
#define ru(i,l,r) for(int i=(l);i<=(r);i++)
#define ru_(i,l,r) for(int i=(l);i<(r);i++)
#define rd(i,l,r) for(int i=(l);i>=(r);i--)

using namespace std;

// 区间遍历计数， 枚举模拟， 子数组枚举， 字符枚举(dp计数)
class Solution{
public:
    int botton(vector<vector<int>>& events){
        map<int,int> ans; int last=0;
        for(auto &t: events){
            int id=t[0], tt=t[1];
            ans[id]=max(ans[id],tt-last); last=tt;
        }
        int mx=0,idx=0;
        for(auto &t: ans){
            if(t.second>mx){mx=t.second; idx=t.first;}
        }; return idx;
    }
};

class Solution2 {
public:
    double maxAmount(string initialCurrency, vector<vector<string>>& pairs1, vector<double>& rates1, vector<vector<string>>& pairs2, vector<double>& rates2) {
        auto calc_amount = [&](vector<vector<string>>& pairs, vector<double>& rates) {
            unordered_map<string, vector<pair<string, double>>> g;
            for (int i = 0; i < pairs.size(); i++) {
                auto& p = pairs[i];
                double r = rates[i];
                g[p[0]].emplace_back(p[1], r);
                g[p[1]].emplace_back(p[0], 1 / r);
            }

            unordered_map<string, double> amount;
            function<void(string, double)> dfs=[&](const string& x, double cur_amount)-> void{
//            auto dfs = [&](this auto&& dfs, const string& x, double cur_amount) -> void {
                amount[x] = cur_amount;
                for (auto& [to, rate] : g[x]) {
                    // 每个节点只需递归一次（重复递归算出来的结果是一样的，因为题目保证汇率没有矛盾）
//                    if (!amount.contains(to)) {
                    if(amount.find(to)==amount.end()){
                        dfs(to, cur_amount * rate);
                    }
                }
            };
            dfs(initialCurrency, 1);
            return amount;
        };

        auto day1_amount = calc_amount(pairs1, rates1);
        auto day2_amount = calc_amount(pairs2, rates2);

        double ans = 0;
        for (auto& [x, a2] : day2_amount) {
            ans = max(ans, day1_amount[x] / a2);
        }
        return ans;
    }
};


int lcs[5010][5010];
class Solution3 {
public:

    int beautifulSplits(vector<int>& nums) {
        int n=nums.size();
        ru(i,0,n) ru(j,0,n) lcs[i][j]=0;
        rd(i,n-1,0) rd(j,n-1,i){
            if(nums[i]!=nums[j]) lcs[i][j]=0;
            else lcs[i][j]=1+lcs[i+1][j+1];
        }
        int ans=0;
        ru(i,1,n-2) ru(j,i+1,n-1){
            int len1=i, len2=j-i, len3=n-j;
            bool ok=len1<=len2&&lcs[0][i]>=len1;
            ok|=(len2<=len3&&lcs[i][j]>=len2);
            ans+=int(ok);
        }
        return ans;
    }
};

class Solution4 {
public:
    int solve(const vector<int> &cnt, int h){
        int ans=0,pre=0;
        vector<vector<int>> dp(26,vector<int>(2,1e9));
        dp[0][0]=cnt[0]; dp[0][1]=abs(cnt[0]-h);
        ru_(i,1,26){
            dp[i][0]=min(dp[i-1][0], dp[i-1][1])+cnt[i];
            if(cnt[i]>h) dp[i][1]=min(dp[i-1][0], dp[i-1][1])+cnt[i]-h;
            else{
                int need=h-cnt[i], ret=1e9;
                {int p=cnt[i-1]; int tmp=dp[i-1][0]+need-min(p,need); ret=min(ret,tmp);}
                {int p=max(cnt[i-1]-h,0); int tmp=dp[i-1][1]+need-min(p,need); ret=min(ret,tmp);}
                dp[i][1]=ret;
            }
        }; return min(dp[25][0], dp[25][1]);
    }
    int makeStringGood(string s) {
        int n=s.length(); vector<int> cnt(26);
        ru_(i,0,n) cnt[s[i]-'a']++;
        int ans=n;
        ru(i,1,n) ans=min(ans,solve(cnt,i));
        return ans;
    }
};

int main(){
    Solution s1;
    vector<vector<int>> e={{1,2},{2,5},{3,9},{1,15}};
    cout<< s1.botton(e)<<endl;

    Solution2 s2;
    string initialCurrency = "EUR";
    vector<vector<string>> pairs1 = {{"EUR","USD"},{"USD","JPY"}};
    vector<double> rates1 = {2.0,3.0};
    vector<vector<string>> pairs2 = {{"JPY","USD"},{"USD","CHF"},{"CHF","EUR"}};
    vector<double> rates2 = {4.0,5.0,6.0};
    cout<<s2.maxAmount(initialCurrency, pairs1, rates1, pairs2, rates2)<<endl;

    Solution3 s3;
    vector<int> nums={1,1,2,1};
    cout<<s3.beautifulSplits(nums)<<endl;

    Solution4 s4;
    string s="acab";
    cout<<s4.makeStringGood(s)<<endl;
    return 0;

    // 30mins
}